1. Field of the Invention
The present invention relates to a distributed system, a memory management device and method, and to a storage medium, and in particular to memory management for distributed computing.
2. Description of the Related Art
An automatic memory management device and memory management method for distributed computing is considered with the purpose of realizing automatic memory management and garbage collection, not in one single memory space, but in a plurality of memory spaces in a distributed system.
In a paper by D. I. Bevan, "Distributed Garbage Collection Using Reference Counting" (Springer Verlag, LN CS 259, June 1987, pages 176-187), an automatic memory management device that uses a weighted reference counting method manages memory by adding a "reference weight," a numerical value, to objects that reference, i.e., that remote-reference, objects in a different memory space.
In a case in which an object is created that has a remote reference to another object, an initial value of a numerical value (exponentiation of 2) particular to an object and referred to as "total reference weight" is set to the referenced object that is remotely referenced; and a numerical value particular to remote referencing to a referenced object, which is referred to as "partial reference weight," is set to the referencing object that remote-references. Remote reference is thus "created."
In FIG. 1, for example, if the initial value for total reference weight is "64," referenced object 11 holds a total reference weight of "64" and reference object 10 that remote-references referenced object 11 has a partial reference weight of "64" with respect to referenced object 11.
In a case in which a reference object that remotely references an object gives information of the referenced object to a third object by means of a communication message, the reference object subtracts half of its own partial reference weight and updates its new partial reference weight as half. The reference object includes the other half of the reference weight in the communication message to the third object.
The third object accepts the reference weight contained in this communication message and stores the received reference weight as its own partial reference weight. In this way, a reference object can make a reference to a referenced object, and remote reference can be "distributed" from a reference object to a third object.
A difference exists between the "distribution" of remote reference and the "creation" of remote reference in that a third object that receives "distribution" of reference resides in a different memory space than the memory space of the reference object that distributes weight and the memory space of the referenced object. In "distribution" of remote reference, moreover, the total reference weight is constant, and the total reference weight is therefore always equal to the sum of the partial reference weights belonging to reference objects and the sum of reference weight pertaining to objects contained in all communication messages that flow in a distributed system.
For example, in a case in which reference object 10 from the state in FIG. 1 transfers the information of referenced object 11 to object 12, reference object 10 decreases its own partial reference weight "64" by half to "32" as shown in FIG. 2. Reference object 10 includes its decreased weight "32" in a communication message and sends this to object 12. Upon accepting this communication message, object 12 makes its own partial reference weight "32" and becomes a reference object as shown in FIG. 3.
When a reference object is no longer necessary in the memory space in which it resides, it transmits to a referenced object a reference deletion message containing information of it own partial reference weight. This "deletion" of remote referencing enables reclamation of unneeded memory region and reuse.
In FIG. 4, for example, when it is determined that reference object 10 having a partial reference weight of "32" is no longer necessary, a reference deletion message containing the reference weight "32" is transmitted to referenced object 11, which is the reference destination. Upon receiving this reference deletion message, referenced object 11 updates by subtracting the received reference weight "32" from the total reference weight, as shown in FIG. 5. When the total reference weight of a referenced object becomes "0," it can be determined that there are no longer any objects referencing the object from other memory spaces. If there is no referencing from the memory region in which the referenced object itself resides, the regions of that referenced object can be reclaimed.
A reference object having a partial reference weight that has become "1" cannot "distribute" remote referencing. In such a case, the reference object creates a new indirect object that indirectly remote-references and causes the created indirect object to indirectly remote-reference.
In FIG. 6, for example, when reference object 20 having a partial reference weight that has become "1" "distributes" remote referencing to object 22, reference object 20 creates indirect object 23 as shown in FIG. 7. Indirect object 23 takes over the partial reference weight of "1" of reference object 20. Indirect object 23 maintains the reference to referenced object 21 and stores a total reference weight of "64." Reference object 20 updates remote referencing from referenced object 21 to indirect object 23, and makes the partial reference weight "64."
Reference object 20 distributes the reference weight by sending a message containing weight "32" to object 22. After accepting this reference weight, object 22 can remote-reference indirect object 23 with a partial reference weight of "32" as shown in FIG. 8.
Nevertheless, the automatic memory management device of the above-described prior art (hereinafter referred to as "the prior art") has the following problems.
First, the prior art cannot realize memory management when the data region of, for example, an object, is migrated between computers.
In recent years, a method referred to as "agent" is being studied in which the execution of an object is resumed or the execution environment of an object is migrated from a particular execution environment to a different execution environment in a network.
In an agent method, the data region itself of an object, or the memory region itself that is occupied by the agent, changes its execution environment, i.e., the region migrates.
In a distributed system in which an agent or an object region accompanying this agent migrates in this way, automatic memory management is necessary to enable an object that referenced an object before migration to continue to reference the object after migration, despite the migration of the referenced object.
In the prior art, however, it was assumed that data regions of, for example, objects, are stationary in the memory space in which they were created. The prior art therefore did not consider even the existence of migrating objects, and memory management of such objects was therefore impossible.
A second problem in the prior art is the increase in the amount of communication in the network.
In a distributed system made up of a wide range of networks such as the Internet, objects increasingly reference data regions of different computers from remote computers. This trend is further increased by the agent migration and object migration described in regard to the first problem.
In addition, due to agent migration and object migration, the situation frequently occurs that the actual data do not reside at the reference destination of maintained data, but can only be referenced after tracing yet another reference destination.
To reference data regions on a computer at a remote site, a reference request communication message must be sent to the computer of the reference destination to have the requested data sent back. A multi-step exchange of communication therefore takes place for an object to reference the actual data.
Reference destinations should be updated to direct reference destinations whenever possible to prevent multi-step communication. However, it has been difficult to reduce the amount of communication necessary for updating reference destinations.
A third problem in the prior art is the depletion of the reference weight used for managing objects (i.e., the reference weight value is used up and can no long be distributed to other objects).
This depletion occurs because, as reference to the same objects increases in the prior art, reference weight can only decrease as long as references are not deleted and returned for reclamation.
A fourth problem in the prior art is the lack of sufficient memory at each individual computer.
In the prior art, indirect objects are created when reference weight is depleted. A large number of indirect objects are created in memory when weight is frequently used up, and this leads to insufficient memory.
A fifth problem in the prior art is the hindrance of high-speed execution of application programs or even the halting of application programs.
This problem occurs because, as with the fourth problem, indirect objects are created when the reference weight is used up, and the creation of many indirect objects leads to the increase in transmission of messages between reference objects and indirect objects.